//
// Created by liushuai on 2021/1/24.
//

#include "addBinary.h"
string addBinary(string a, string b) {
    int max_size = a.size();
    int min_size = b.size();
    string result = "";
    stack<int> char_stack;
    if(max_size<min_size){
        max_size = b.size();
        min_size = a.size();
    }
    if(max_size==0)
        return result;
    int forward = 0;
    int current = 0;
    for(int i=0;i<min_size;i++){
        int last_elem_a = a[a.size()-1-i]-'0';
        int last_elem_b = b[b.size()-1-i]-'0';
        current = last_elem_a+last_elem_b+forward;
        forward = current/2;
        char_stack.push(current%2+'0');
    }
    for(int i=max_size-min_size-1;i>=0;i--){
        if(a.size()>b.size()){
            current = a[i]+forward-'0';
        }else{
            current = b[i]+forward-'0';
        }
        forward = current/2;
        char_stack.push(current%2+'0');
    }
    if(forward)
        char_stack.push('1');
    while (!char_stack.empty()){
        result+=char_stack.top();
        char_stack.pop();
    }
    return result;
}